package leetcode_1_20;

import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.Collectors;

public class longestPalindrome_5 {
    /**
     * 5，最长回文子串, 通过正则表达式，leetcode不识别Pattern类就很搞
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        String maxSubstring =new String(); //实时最大回文子串
        List Substring=new ArrayList<>();
        char[] arr=s.toCharArray();
        int len=arr.length;
        String p1="(\\w)\\1";        //正则模式1 ， 匹配两个连续相同的字符，aa
        String p2="(\\w)(\\w)\\1";  //匹配类似aba
        Pattern pattern1 = Pattern.compile(p1);
        Pattern pattern2 = Pattern.compile(p2);
        Matcher matcher1=pattern1.matcher(s);
        Matcher matcher2=pattern2.matcher(s);
        //aa类型
        while(matcher1.find()) {
            int t=0;       //Substring的起始索引
            Substring=matcher1.group(0).chars()
                    .mapToObj(c -> (char) c)
                    .collect(Collectors.toList());
            int start=matcher1.start();
            int end=matcher1.end();
            int e=end,sta=start;
            while ( e != len  ){
                if(arr[e] == (char)Substring.get(t+1)){
                    Substring.add(arr[e]);
                    t++;
                    e++;
                }
                else if(sta !=0 && arr[e ] == arr[sta-1]){
                    Substring.add(0,arr[ e ]);
                    Substring.add(arr[ e ]);
                    sta--;
                    e++;
                }
            }
            if(Substring.size()>maxSubstring.length())
                maxSubstring=Substring.toString();
        }
        while(matcher2.find()){
            //aba类型
            int t=0;
            Substring=matcher2.group(0).chars()
                    .mapToObj(c -> (char) c)
                    .collect(Collectors.toList());
            int start=matcher2.start();
            int end=matcher2.end();
            int e=end,sta=start;
            while ( end != len && sta !=0 && arr[e] == arr[sta-1]){
                Substring.add(0,arr[ e ]);
                Substring.add(arr[ e ]);
                sta--;
                e++;
            }
            if(Substring.size()>maxSubstring.length())
                maxSubstring=Substring.toString();
        }
        return maxSubstring.toString();
    }

    /**
     * 5.1，最长回文子串, 通过Manacher算法
     * @param s
     * @return
     */
    public static String longestPalindrome1(String s) {
        char[] init=s.toCharArray();
        char[] arr=new char[3000];        //构造新的字符串
        arr[0]='$';                               //避免索引出界
        int len[]=new int[3000];            //len[i]表示以arr[i]为中心的回文串半径
        for (int i:len)
            len[i]=0;
        int s_lenth = s.length(), t = 1;
        //加入符号#分隔  $#a#b#a#$
        for(int i=0;t<s_lenth*2+2;t++){
            if(t%2!=0) arr[t]='#';
            else
                arr[t] = init[i++];
        }
        arr[s_lenth*2+2]='$';               //避免索引出界
        int reCenter=0 ; // 结果最大回文串中心下标
        int relen=0;        // 最长回文半径
        int id= 1;            // 当前R所属回文串中心下标
        int R = 0;            // 最长回文直径有效位置的下一个位置
        if(s_lenth==1)
            return s;
        for(int i=1; i<t-1; i++){
            // 2*id - i 即与 i 对称位置的 j 的下标
            int x=R - i,y=len[ 2*id - i ],z ;
            if(x<y)
                z=x;
            else
                z=y;
            len[i] =R > i ? z : 1;
            //len[i] =R > i ? min( R - i , len[ 2*id - i ] ) : 1;
            /**只能确定i~mx的回文情况
             如果上一个回文串的最右元素下标大于当前字符下标
             说明该元素包含在上一个回文串中，
             比较min(R - i , len[2*id - i])即是比较 j 的范围是否超过了上一个回文串左边尽头，
             超过即代表 i 不能直接用 j 的数据，但可以先直接赋值 R - i 到回文串的尽头，再继续匹配
             不超过利用对称性直接得到len[i]
             否则则按新串进行处理，赋值为1**/
            while(arr[i+len[i]] == arr[i-len[i]] && i-len[i]!=0)
                len[i]++;
            /**
             * 进行判定，如果向右len[i]个元素，即最右侧和最左侧字符相等
             * 则len[i]++，直到遇到不相等的字符停止
             */
            //当匹配的字符下表超过 R 时 R 和 id 就更新，因为上一个回文串右范围已经低于当前回文串了
            if(i+len[i] > R){
                R = i+len[i];
                id = i;
            }
            //如果当前子串长度大于最大回文串长度，则更新
            if(len[i]>relen) {
                reCenter=i;
                relen=len[i];
            }
        }
        int a=( reCenter - (relen-1) +1 - 2) / 2 ,b = a + (relen - 1) - 1;
        return String.copyValueOf(init).substring(a,b+1);  //b+1 是因为subString不截取最后一位
        //转化为字符串后进行截取
    }

}
